package com.shuang.link2;

public class MyLinkedList {

    //单链表 虚拟头节点


    //用于记录链表大小（链表中元素个数）
    private int size;

    //链表的虚拟头节点
    private ListNode vHead;

    //初始化自定义链表
    public MyLinkedList() {
        this.size = 0;
        this.vHead = new ListNode(0);
    }

    //根据索引位置得到索引位置的元素 索引0是第一个元素
    public int get(int index) {

        //下标无效则返回-1
        if (index < 0 || index >= size){
            return -1;
        }

        //下标有效
        ListNode curr = new ListNode();
        curr = vHead;

        //让curr指向要取的索引位置的元素
        for (int i = 0; i <= index; i++){
            curr = curr.next;
        }
        return curr.val;
    }

    //将一个值为 val 的节点插入到链表中第一个元素之前，在插入完成后，新节点会成为链表的第一个节点
    public void addAtHead(int val) {

        //插入的新节点
        ListNode newNode = new ListNode(val);

        newNode.next = vHead.next;
        vHead.next = newNode;

        //链表插入一个元素 长度加一
        size++;
    }

    //将一个值为 val 的节点追加到链表中作为链表的最后一个元素
    public void addAtTail(int val) {

        //插入的新节点
        ListNode newNode = new ListNode(val);

        //用于遍历链表 找到最后一个元素位置
        ListNode curr = vHead;

        while (curr.next != null) {
            curr = curr.next;
        }

        curr.next = newNode;

        size++;

    }

    //将一个值为 val 的节点插入到链表中下标为 index 的节点之前。如果 index 等于链表的长度，那么该节点会被追加到链表的末尾(索引为链表长度节点的前一个位置)。如果 index 比长度更大，该节点将不会插入到链表中
    public void addAtIndex(int index, int val) {

        //索引大于链表长度则直接返回
        if (index > size) {
            return;
        }

        //用于找到索引位置之前的元素位置
        ListNode pre = vHead;

        for (int i = 0; i < index; i++) {
            pre = pre.next;
        }

        //新节点
        ListNode newNode = new ListNode(val);
        //插入节点
        newNode.next = pre.next;
        pre.next = newNode;

        size++;
    }

    //如果下标有效，则删除链表中下标为 index 的节点。
    public void deleteAtIndex(int index) {

        //无效下标
        if (index < 0 || index >= size) {
            return;
        }

        //有效下标
        //用于找到索引位置之前的元素位置
        ListNode pre = vHead;
        for (int i = 0; i < index; i++) {
            pre = pre.next;
        }

        pre.next = pre.next.next;

        size--;
    }
}
